package demo1;

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
      ListNode minH = null ;
      ListNode minE = null ;
      ListNode bigH = null ;
      ListNode bigE = null ;
     ListNode cur = pHead ;
      
      while(cur != null){
       if(cur.val < x){
        if(minH == null){
            minH = cur ;
            minE = cur ;
        }else{
           minE .next = cur ;
           minE = minE.next ;
        }
       }else{
         if(bigH == null){
            bigH = cur ;
            bigE = cur ;
         }else{
            bigE.next = cur ;
             bigE = bigE .next ;
         }
       }
          cur = cur.next ; 
      }
    
      if(minH == null){
        return bigH ;
      }
         if(bigH == null){
            return minH ;
        }
        minE.next = bigH ;
          bigE.next = null ;
          return minH ;
    }
}